/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-03-25
 * Time: 19:06
 */
class Solution {
    //打家劫舍问题1
    public int massage(int[] num) {
        //1.创建dp表
        //dp[i]表示选择到i位置的最长预约时长
        //可以细分为f[i]选择到i位置的时候,必选num[i]最长预约时长
        //g[i]选择到i位置的时候,不选num[i]最长预约时长
        int n = num.length;
        //处理边界
        if(n == 0) {
            return 0;
        }
        int[] f = new int[n];
        int[] g = new int[n];
        //2.初始化
        f[0] = num[0];g[0] = 0;
        //3.遍历顺序 从左往右
        //4.状态转移
        for(int i = 1; i < n; i++) {
            f[i] =  g[i-1]+num[i];
            g[i] = Math.max(g[i-1],f[i-1]);
        }
        //5.返回值
        return Math.max(f[n-1],g[n-1]);
    }

    //打家劫舍问题2 多加条件:首尾相连,根据首位选择与否来分情况讨论
    public int rob(int[] nums) {
        int n = nums.length;
        return Math.max(nums[0]+rob1(nums,2,n-2),rob1(nums,1,n-1));
    }

    public int rob1(int[] nums, int left, int right) {
        if(left > right) {
            return 0;
        }
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[left] = nums[left];
        for(int i = left+1; i <= right; i++) {
            f[i] = g[i-1]+nums[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        return Math.max(f[right],g[right]);
    }

    //删除并获得点数
    //也是转化成“打家劫舍”问题,先进行预处理
    public int deleteAndEarn(int[] nums) {
        //1.预处理
        int n = nums.length, m = nums[0];
        for(int i = 0; i < n; i++) {
            m = Math.max(m,nums[i]);
        }
        int[] arr = new int[m+1];
        for(int i = 0; i < n; i++) {
            arr[nums[i]] += nums[i];
        }
        //2.与"打家劫舍"一致
        int[] f = new int[m+1];
        int[] g = new int[m+1];
        f[0] = arr[0];g[0] = 0;
        for(int i  = 1; i <= m; i++) {
            f[i] = g[i-1]+arr[i];
            g[i] = Math.max(g[i-1],f[i-1]);
        }
        return Math.max(f[m],g[m]);
    }
}
